﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm
{
    class Tiling
    {
        public Tiling()
        {
            int testCase = GetConsole.GetInt();
            while (testCase-- > 0)
            {
                long width = GetConsole.GetInt();
                NoLimitNumber a = new NoLimitNumber(1);
                NoLimitNumber b = new NoLimitNumber(3);
                if (width == 1)
                {
                    Console.WriteLine("1");
                    continue;
                }
                if (width == 2)
                {
                    Console.WriteLine("3");
                    continue;
                }
                NoLimitNumber value = new NoLimitNumber(0);
                for (int i = 2; i < width; i++)
                {
                    value = b + (a * 2);
                    a = b;
                    b = value;
                }
                Console.WriteLine(value);
            }
        }
    }
    public struct NoLimitNumber
    {
        public List<long> longList; 
        private static long overflowNum = 1000000000000000000;
        public NoLimitNumber(long value)
        {
            longList = new List<long>();
            longList.Add(value);
        }
        public NoLimitNumber(List<long> newList)
        {
            longList = newList;
        }
        public static NoLimitNumber operator +(NoLimitNumber a, NoLimitNumber b)
        {
            if(b.longList.Count > a.longList.Count)
            {
                List<long> buf = a.longList;
                a.longList = b.longList;
                b.longList = buf;
            }
            List<long> newList = new List<long>();
            long carry = 0;
            long sum = 0;
            for (int i = 0; i < b.longList.Count; i++)
            {
                sum = a.longList[i] + b.longList[i] + carry;
                carry = 0;
                if (overflowNum < sum)
                {
                    carry = 1;
                    sum = sum - overflowNum;
                }
                newList.Add(sum);
            }
            for (int i = b.longList.Count; i < a.longList.Count; i++)
            {
                newList.Add(a.longList[i] + carry);
                carry = 0;
            }
            if (carry == 1)
            {
                newList.Add(1);
            }
            return new NoLimitNumber(newList);
        }
        public static NoLimitNumber operator *(NoLimitNumber a, long b)
        {
            List<long> newList = new List<long>();
            long sum = 0;
            long carry = 0;
            for (int i = 0; i < a.longList.Count; i++)
            {
                sum = a.longList[i] * b + carry;
                carry = 0;
                if (sum > overflowNum)
                {
                    carry = 1;
                    sum = sum - overflowNum;
                }
                newList.Add(sum);
            }
            if (carry == 1)
            {
                newList.Add(1);
            }
            return new NoLimitNumber(newList);
        }
        public override string ToString()
        {
            string valueString = string.Empty;
            for (int i = longList.Count - 1; i >= 0; i--)
            {
                valueString += longList[i].ToString();
            }
            return valueString;
        }

    }
}
